package vip.zhenzicheng.algorithm.leetcode.binary_tree;


import vip.zhenzicheng.algorithm.TreeNode;

/**
 * <a href="https://leetcode.cn/problems/balanced-binary-tree/">平衡二叉树 [简单]</a>
 * 定义：一个二叉树的左右两个子树的高度差绝对值不超过1
 * 提示：
 * 树中的节点数在范围 [0, 5000] 内
 * -104 <= Node.val <= 104
 *
 * @author zhenzicheng
 * @date 2022-06-06 12:59
 */
public class BalancedBinaryTree_110 {

  public boolean isBalanced(TreeNode root) {
    if (root == null) {
      return true;
    }

    return helper(root) != -1;
  }

  public int helper(TreeNode root) {
    if (root == null) {
      return 0;
    }

    int left = helper(root.left); // 递归找到最左边的叶子节点
    int right = helper(root.right); // 递归找到最右边的叶子节点
    if (left == -1 || right == -1 || Math.abs(left - right) > 1) {
      return -1;
    }

    return Math.max(left, right) + 1;
  }
}
